package LeetCode;

public class LC_471_EncodeStringwithShortestLength {

    public static void main(String[] args) {

    }

    static class Solution {
        private static int shortestEncodingStringLenth(String s) {
            int n = s.length();
            String[][] dp = new String[n][n];
            for (int i = 0; i < n; i++) {
                dp[i][i] = String.valueOf(s.charAt(i));
            }
            for (int len = 1; len < n; len++) {
                for (int i = 0; i + len < n; i++) {
                    int j = i + len;
                    for (int k = i; k < j; k++) {
                        int left = dp[i][k].length();
                        int right = dp[k + 1][j].length();
                        if (dp[i][j] == null || left + right < dp[i][j].length()) {
                            dp[i][j] = dp[i][k] + dp[k + 1][j];
                        }
                    }
                    String sub = s.substring(i, j + 1);
                    int index = (sub + sub).indexOf(sub, 1);

                    if (index < sub.length()) {
                        sub = (sub.length() / index) + "[" + dp[i][i + index - 1] + "]";
                    }
                    if (dp[i][j] == null || dp[i][j].length() > sub.length()) {
                        dp[i][j] = sub;
                    }
                }
            }
            return dp[0][n - 1].length();
        }
    }

}
